import connectTree.Node;

public class Solution116 {
    /*public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int n = queue.size();
            for (int i = 0; i < n; i++) {
                Node pre = queue.poll();
                assert pre != null;
                pre.next = i == n - 1 ? null : queue.peek();
                if (pre.left != null) {
                    queue.offer(pre.left);
                    queue.offer(pre.right);
                }
            }
        }
        return root;
    }*/

    public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        if (root.left != null) {
            root.left.next = root.right;
            if (root.next != null) {
                root.right.next = root.next.left;
            }
            connect(root.left);
            connect(root.right);
        }
        return root;
    }
}
